package com.ly.algorithm.offerpointer;
import	java.util.PriorityQueue;

import java.util.*;

/**
 * @Classname Offer41
 * @Description
 *
 * [2, 3, 4] 的中位数是 3
 *
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 *
 * 设计一个支持以下两种操作的数据结构：
 *
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 示例 1：
 *
 * 输入：
 * ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
 * [[],[1],[2],[],[3],[]]
 * 输出：[null,null,null,1.50000,null,2.00000]
 * 示例 2：
 *
 * 输入：
 * ["MedianFinder","addNum","findMedian","addNum","findMedian"]
 * [[],[2],[],[3],[]]
 * 输出：[null,null,2.00000,null,2.50000]
 *
 *
 * @Date 2021/1/30 17:52
 * @Author 冷心影翼
 */
public class Offer41 {

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(6);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(10);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(6);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(5);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(6);
        medianFinder.addNum(4);
        medianFinder.addNum(5);
        System.out.println(medianFinder.findMedian());
    }

}


class MedianFinder {

    PriorityQueue<Integer> maxHeap;

    PriorityQueue<Integer> minHeap;

    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((x,y)->y-x);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
      if(maxHeap.size() != minHeap.size()) {
          minHeap.add(num);
          maxHeap.add(minHeap.poll());
      }else {
          maxHeap.add(num);
          minHeap.add(maxHeap.poll());
      }
    }

    public double findMedian() {
        return (maxHeap.size()+minHeap.size())%2 == 0?(maxHeap.peek()+minHeap.peek())/2.0:minHeap.peek();
    }
}
